//
// Created by liushuai on 2021/1/16.
//

#include "longestPalindromeSubseq.h"

int longestPalindromeSubseq(std::string &s) {
    const int n = s.size();
    std::vector<std::vector<int>> dp =
        std::vector<std::vector<int>>(n, std::vector(n, 0));
    for (int start = n - 1; start >= 0; start--) {
        for (int end = start; end < n; end++) {
            if (start == end) {
                dp[start][end] = 1;
            } else {
                if (s[start] == s[end])
                    dp[start][end] = dp[start + 1][end - 1] + 2;
                else
                    dp[start][end] = dp[start + 1][end] > dp[start][end - 1]
                                         ? dp[start + 1][end]
                                         : dp[start][end - 1];
            }
        }
    }
    return dp[0][n - 1];
}
